The present invention relates to apparatus and methods for providing route guidance to vehicles.
Navigation systems which compute a route for a vehicle designed to bring the vehicle from its current location to a desired location are known.
A document entitled xe2x80x9cDynaMIT:Task C Reportxe2x80x9d, posted at MIT website its.mit.edu/projects/dta/Taskc, describes a traffic assignment system and notes, inter alia, that xe2x80x9cIn an (ideal) system . . . where there is two-way communication between the traffic control center and every vehicle in the network, perfect information about the vehicle location and possibly its origin and destination, can be obtained. While such perfect systems are possible in the future, most existing surveillance systems are limited to vehicle detectors located at critical points in the network. The information provided by these traffic sensors therefore must be used to infer traffic flows, queue lengths, incidents, etc., at all locations of the network.xe2x80x9d
Another document discussing pertinent technology and entitled xe2x80x9cDynaMIT:DYnamic network assignment for the management of information to travellersxe2x80x9d is posted at its.mit.edu/projects/dta/dynamit.
Traffic flow theory is a field in which experts endeavor to generate theoretical models of traffic flow in order to make predictions which are helpful in developing services and resources which will best serve traffic requirements. State of the art traffic flow theory is described in xe2x80x9cTransportation Research Board""s Revised Special Reportxe2x80x9d, xe2x80x9cTraffic Flow Theoryxe2x80x9d, available at tfhrc.gov/its/tft/tft/. Development and verification of traffic flow models conventionally do not collect or utilize transmission from mobile communication devices residing in the vehicles within the traffic under investigation.
The Nokia 5100 and 6100 mobile phone series display their own current status, including an xe2x80x9cin vehiclexe2x80x9d status.
The disclosures of all publications mentioned in the specification and of the publications cited therein are hereby incorporated by reference.
The present invention seeks to provide an improved route guidance system.
There is thus provided, in accordance with a preferred embodiment of the present invention, a traffic monitoring system including traffic data collection apparatus operative to collect location data from a plurality of users of mobile communication devices, and a traffic data filter operative to analyze the location data arriving from the plurality of users and to reject location data which is not traffic data.
Preferably, the traffic data filter includes a traffic element identifier operative to identify traffic elements within the plurality of users by analyzing the location data arriving from the plurality of users.
Further in accordance with a preferred embodiment of the present invention, the location data includes a sequence of at least one time-stamped locations.
Still further in accordance with a preferred embodiment of the present invention, the traffic data filter is operative to accept, as traffic data, the location data arriving from users who have identified themselves as traffic elements.
Also provided, in accordance with another preferred embodiment of the present invention, is a traffic monitoring system including location collection apparatus operative to collect location data from at least a traffic population including a multiplicity of traffic elements, the multiplicity of traffic elements including a plurality of users of mobile communication devices, a location data analyzer operative to analyze the location data and to derive traffic information therefrom, and a traffic information disseminator operative to provide at least some of the traffic population with the traffic information.
Further in accordance with a preferred embodiment of the present invention, the location data analyzer is operative to derive, for at least one traffic element, at least a portion of a road route followed by the traffic element.
Still further in accordance with a preferred embodiment of the present invention, the location data defining the location of a mobile communication device at time t is based on an identification of a mobile communication cell serving the mobile communication device at time t.
Additionally in accordance with a preferred embodiment of the present invention, the location data defining the location of a mobile communication device at time t is based only on an identification of a mobile communication cell serving the mobile communication device at time t.
Also provided, in accordance with still another preferred embodiment of the present invention, is a traffic monitoring method including collecting location data from a plurality of users of mobile communication devices, and analyzing the location data arriving from the plurality of users and rejecting location data which is not traffic data.
Further in accordance with a preferred embodiment of the present invention, the method also includes rejecting location data indicating a too-large discrepancy between a current location of a vehicle and its stored previous locations.
Further in accordance with a preferred embodiment of the present invention, the system also includes a user location database storing, for each mobile communication device from which readings have been received, the ID of that device and each of the readings received, each with its own time-stamp.
Still further in accordance with a preferred embodiment of the present invention, the system also includes a road traffic database storing, for at least one road, velocity profiles computed for that road, each profile being stored with its own time-stamp.
Also provided, in accordance with still another preferred embodiment of the present invention, is a traffic monitoring system for monitoring traffic including a population of users bearing a multiplicity of mobile communication devices, the system including a mobile communication network interface receiving, from at least one communication network serving the multiplicity of mobile communication devices, and storing, location information characterizing at least some of the multiplicity of mobile communication devices, and a traffic monitor operative to compute at least one traffic-characterizing parameter on the basis of the location information.
Further in accordance with a preferred embodiment of the present invention, the traffic monitor is also operative to display the at least one traffic-characterizing parameter.
Still further in accordance with a preferred embodiment of the present invention, the mobile communication devices include cellular communication devices served by at least one cellular communication network including a plurality of base stations each serving a cell including a portion of a geographical area.
Additionally in accordance with a preferred embodiment of the present invention, the location information includes indications of cells serving at least some of the multiplicity of mobile communication devices.
Further in accordance with a preferred embodiment of the present invention, the system also includes a road database storing locations of roads in a geographical area.
Still further in accordance with a preferred embodiment of the present invention, the system also includes a road database storing locations of roads in a geographical area, wherein the traffic monitor is operative to deduce, based on at least one indication of a cell in which a mobile communication device is located, a road which the mobile communication device is believed to be taking.
Further in accordance with a preferred embodiment of the present invention, the traffic monitor is operative, based on an indication that an individual mobile communication device is travelling through a cell sequence including at least one cell, to differentiate a first road portion along which the individual mobile communication device is travelling, from a second road portion falling along the same cell sequence, along which the mobile communication device is not travelling.
Still further in accordance with a preferred embodiment of the present invention, the traffic monitor is operative to differentiate the first and second road portions by estimating at least one traffic parameter for the first and second road portions which parameter has different values for the first and second road portions.
Further in accordance with a preferred embodiment of the present invention, at least some traffic characterizing information is generated using communication cell ID-based location information which is at communication cell ID accuracy.
Still further in accordance with a preferred embodiment of the present invention, the traffic monitor is operative to identify a set of mobile communication devices suspected of be served by a cell other than the cell in which they are actually located and to verify at least some location information arriving from at least some of the mobile communication devices in the set.
Also in accordance with a preferred embodiment of the present invention, the at least one traffic-characterizing parameter includes at least one of the following group of parameters: a travel time parameter, a traffic speed parameter, a traffic density parameter, and a traffic flow parameter.
Further in accordance with a preferred embodiment of the present invention, the system also includes at least one historical database storing historical location information characterizing past distributions of users over a geographical area of interest, and the traffic monitor is, at least on occasion, operative to compute the at least one traffic-characterizing parameter at least partly on the basis of the historical location information.
Still further in accordance with a preferred embodiment of the present invention, the traffic monitor is operative to evaluate the quality of location information on the basis of which the traffic-characterizing parameter is to be computed and to employ the historical location information if the quality is found to be relatively low.
Additionally in accordance with a preferred embodiment of the present invention, the quality of location information is evaluated at least partly as a function of the number of users providing current location information.
Further in accordance with a preferred embodiment of the present invention, the mobile communication network interface receives and stores location information from cellular communication devices served by more than one cellular communication network.
Still further in accordance with a preferred embodiment of the present invention, the system also includes a mobile user pinpointing function operative to deduce, from information at communication cell ID accuracy, location information which is at an accuracy higher than communication cell ID accuracy, by combining the communication cell ID accuracy information with additional stored information.
Further in accordance with a preferred embodiment of the present invention, the additional stored information includes information regarding intersections between cells and roads.
Still further in accordance with a preferred embodiment of the present invention, the additional stored information includes information regarding a sequence of cells through which a user has passed.
Additionally in accordance with a preferred embodiment of the present invention, the mobile communication network interface receives at least some of the location information used by the traffic monitor, from a base station.
Further in accordance with a preferred embodiment of the present invention, the mobile communication network interface receives at least some of the location information used by the traffic monitor, from a CDR database.
Still further in accordance with a preferred embodiment of the present invention, the mobile communication network interface receives at least some of the location information used by the traffic monitor, from a location server.
Further in accordance with a preferred embodiment of the present invention, the mobile communication network interface receives at least some of the location information used by the traffic monitor, directly from at least some of the multiplicity of mobile communication devices.
Still further in accordance with a preferred embodiment of the present invention, at least some of the location information is provided responsive to a cell broadcast.
Additionally in accordance with a preferred embodiment of the present invention, at least some of the location information is provided responsive to a data transmission directed to individual ones of the multiplicity of mobile communication devices.
Further in accordance with a preferred embodiment of the present invention, the data transmission includes an SMS message.
Still further in accordance with a preferred embodiment of the present invention, at least some of the location information provided by the mobile communication devices is provided in SMS format.
Additionally in accordance with a preferred embodiment of the present invention, the mobile communication network interface also receives and stores travel time information and the traffic monitor is operative to compute at least one traffic-characterizing parameters on the basis of at least the travel time information.
Further in accordance with a preferred embodiment of the present invention, the location information does not violate the privacy of the users of the mobile communication devices.
Still further in accordance with a preferred embodiment of the present invention, the system also includes a congestion detector operative to detect at least one of generation and dissipation of mobile communication device congestion.
Additionally in accordance with a preferred embodiment of the present invention, the system also includes a congestion-anticipation based cellular network resource allocator operative to receive a congestion-indicative output from the congestion detector and to allocate resources accordingly.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including monitoring traffic information characterizing traffic flowing along at least one routes, and computing and reporting to a traveller, information characterizing the traveller""s expected travel time along each of the at least one routes.
Further in accordance with a preferred embodiment of the present invention, the method also includes providing an origin location and a destination location and computing at least one routes connecting the origin and destination locations.
Further in accordance with a preferred embodiment of the present invention, the computing step includes recomputing, at least once, information characterizing the traveller""s remaining travel time along the route, as the traveller travels along the route.
Still further in accordance with a preferred embodiment of the present invention, the computing and reporting step includes reporting the information to the traveller only if the information deviates, in accordance with a predetermined deviation criterion, from a known travel time value.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including monitoring the speed of traffic flowing through a geographical area, and generating a warning if there is a substantial change in the speed of traffic flowing through a portion of the geographical area.
Further in accordance with a preferred embodiment of the present invention, the method also includes storing information regarding personal driving habits of the traveller and wherein the computing and reporting step includes computing the information characterizing the traveller""s expected travel time at least partly based on the information regarding the traveller""s personal driving habits.
Further in accordance with a preferred embodiment of the present invention, the information regarding personal driving habits includes information characterizing travel time along a road sequence not monitored in the monitoring step.
Still further in accordance with a preferred embodiment of the present invention, the computing and reporting step includes reporting to the driver in IVR (interactive voice response) format.
Still further in accordance with a preferred embodiment of the present invention, the computing and reporting step includes reporting to the driver in a data transmission format.
Further in accordance with a preferred embodiment of the present invention, the data transmission format includes SMS (short message service).
Still further in accordance with a preferred embodiment of the present invention, the data transmission format includes WAP (wireless application protocol) format.
Further in accordance with a preferred embodiment of the present invention, the origin and destination locations are received from the driver.
Still further in accordance with a preferred embodiment of the present invention, the providing step includes setting the origin of the route to the current location of the driver.
Further in accordance with a preferred embodiment of the present invention, monitoring the current location of the driver is based on determining a cellular location of a mobile communication device riding with the driver.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including monitoring traffic information characterizing traffic flowing along a route taken by a driver, including monitoring the current location of the driver, and computing information characterizing the driver""s expected progress along the route and reporting the information to the driver when the driver arrives at a predetermined location along the route.
Also provided, in accordance with still another preferred embodiment of the present invention, is a directed advertisement method including receiving an indication from a travelling user of his desired destination, and providing advertisement content to the travelling user based on the desired destination.
Further in accordance with a preferred embodiment of the present invention, the advertisement providing step includes computing a recommended route to the desired destination and reporting the recommended route to the travelling user, and providing advertisement content to the travelling user which pertains to the recommended route.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance system including a traffic velocity computer operative to receive the following information: a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating a moving vehicle""s current location from the selected destination, and a route assigned to at least one vehicle within the traffic, and to compute at least one velocity characteristic of the traffic, and a route selecting computer operative to receive a selected destination of the moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the at least one velocity characteristic.
Also provided, in accordance with yet another preferred embodiment of the present invention, is a traffic velocity monitoring system including a representation of an area in which traffic travels, a vehicle location monitor operative to receive vehicle location information, from a multiplicity of moving vehicles, as to their current location, and a per-vehicle velocity computer operative to derive, from the vehicle location information and the representation, an average velocity of at least one individual moving vehicle from among the multiplicity of moving vehicles.
Further in accordance with a preferred embodiment of the present invention, the system also includes a global velocity computer operative to receive average velocities of each of a plurality of vehicles from the per-vehicle velocity computer and to compute therefrom an average velocity of traffic including the plurality of vehicles.
Also provided, in accordance with a preferred embodiment of the present invention, is a route guidance system including a traffic information accumulator operative to accumulate up-to-date traffic characterizing information characterizing traffic including a route assigned to at least one vehicle within the traffic, and a route selecting computer operative to compute a route from a moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the traffic characterizing information.
Further in accordance with a preferred embodiment of the present invention, the route computed by the route selecting computer is fed back to the traffic information accumulator and is employed by the accumulator to generate anticipated traffic information estimating characteristics of traffic separating a future location of the moving vehicle from the moving vehicle""s selected destination.
Still further in accordance with a preferred embodiment of the present invention, the route selecting computer includes a dynamic route selecting computer operative to provide the moving vehicle with ongoing modifications of the route at least partly as a function of the anticipated traffic information.
Further in accordance with a preferred embodiment of the present invention, the route selecting computer randomly selects at least a portion of at least one vehicle""s route from among several candidate route portions for that vehicle, the random selection being biased by the relative merits of the candidate route portions for the vehicle.
Still further in accordance with a preferred embodiment of the present invention, the traffic information accumulator is also operative to receive up-to-date information characterizing road conditions in road segments separating the vehicle""s current location from the vehicle""s selected destination.
Further in accordance with a preferred embodiment of the present invention, the road conditions include permanent road conditions and/or transient road conditions.
Still further in accordance with a preferred embodiment of the present invention, the transient road conditions include states of multi-state traffic governing elements.
Further in accordance with a preferred embodiment of the present invention, the multi-state traffic governing elements include at least one of the following: a traffic light having more than one possible schedule, and a digital sign displaying any of a plurality of route-guiding messages.
Still further in accordance with a preferred embodiment of the present invention, the traffic information accumulator is operative to provide information to the multi-state traffic governing elements and the multi-state traffic governing elements are operative to select a state at least partly in response to the information.
Further in accordance with a preferred embodiment of the present invention, the accumulator includes a traffic flow simulator operative to generate at least some of the anticipated traffic information.
Still further in accordance with a preferred embodiment of the present invention, the traffic characterizing information includes quantitative information.
Further in accordance with a preferred embodiment of the present invention, the route selecting computer includes a multiplicity of independent route selecting units located within each of a multiplicity of vehicles respectively.
Still further in accordance with a preferred embodiment of the present invention, the route selecting computer includes a central unit operative to compute a route for each of a multiplicity of vehicles and to transmit each vehicle""s route to that vehicle.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance system including a traffic velocity computer operative to accept a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating the moving vehicle""s current location from the selected destination, and to compute at least one velocity characteristic of the traffic, and a route selecting computer operative to receive a selected destination of a moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the at least one velocity characteristic.
Further in accordance with a preferred embodiment of the present invention, the route selecting computer is operative to compute and display an estimated arrival time for the moving vehicle.
Further in accordance with a preferred embodiment of the present invention, the system also includes a route display unit operative to display to a driver of the moving vehicle, at least one directive derived from the route.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including receiving the following information: a selected destination of a moving vehicle, a current location of the moving vehicle, and a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating the moving vehicle""s current location from the selected destination, and a route assigned to at least one vehicle within the traffic, computing at least one velocity characteristic of the traffic, and computing a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the at least one velocity characteristic.
Also provided, in accordance with another preferred embodiment of the present invention, is a traffic velocity monitoring method including providing a representation of an area in which traffic travels, receiving vehicle location information, from a multiplicity of moving vehicles, as to their current location, and deriving, from the vehicle location information and the representation, an average velocity of at least one individual moving vehicle from among the multiplicity of moving vehicles.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including accumulating up-to-date information characterizing traffic including a route assigned to at least one vehicle within the traffic, and computing a route from a moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the traffic characterizing information.
Further provided, in accordance with still another preferred embodiment of the present invention, is a route guidance method including providing the following information: a selected destination of a moving vehicle, a current location of the moving vehicle, and a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating the moving vehicle""s current location from the selected destination, computing at least one velocity characteristic of the traffic, and computing a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the at least one velocity characteristic.
Also provided, in accordance with still another preferred embodiment of the present invention, is a route guidance system including a traffic quantifier operative to receive the following information: traffic location information describing a location of at least one vehicle within traffic separating a moving vehicle""s current location from the selected destination, and a route assigned to at least one vehicle within the traffic, and to compute at least one quantitative characteristic of the traffic, and a route selecting computer operative to receive a selected destination of the moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the at least one quantitative characteristic.
Further provided, in accordance with still another preferred embodiment of the present invention, is a route guidance method including receiving the following information: a selected destination of a moving vehicle, a current location of the moving vehicle, and a route assigned to at least one vehicle within the traffic, computing at least one quantitative characteristic of the traffic, and computing a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the at least one quantitative characteristic.
Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance system including a traffic quantification computer operative to provide a quantitative characterization of traffic separating the moving vehicle""s current location from the selected destination, and a route selecting computer operative to receive a selected destination of a moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle""s current location to the moving vehicle""s selected destination, at least partly as a function of the quantitative characterization.
Further in accordance with a preferred embodiment of the present invention, the method also includes employing a global average velocity of a sample of moving vehicles to estimate average velocity of traffic.
Still further in accordance with a preferred embodiment of the present invention, the traffic characterizing information employed by the route selecting computer includes information regarding anticipated traffic.
Further in accordance with a preferred embodiment of the present invention, at least one of the plurality of locations is computed by a digital cellular operator.
Still further in accordance with a preferred embodiment of the present invention, at least one of the plurality of locations includes GPS information.
Further in accordance with a preferred embodiment of the present invention, the route selecting computer is operative to receive the moving vehicle""s current location from a digital cellular operator.
Further in accordance with a preferred embodiment of the present invention, the route selecting computer takes into account at least one road characteristic affecting average traffic speed.
Still further in accordance with a preferred embodiment of the present invention, the road characteristic includes a time-dependent road characteristic and/or a permanent road characteristic.
Also provided, in accordance with another preferred embodiment of the present invention, is a method for monitoring a population of users bearing mobile communication devices, the method including receiving information from a user bearing a mobile communication device which is indicative of his destination, and accumulating the information and providing the information to at least one element serving the population of users.
Further in accordance with a preferred embodiment of the present invention, the user bearing a mobile communication device is a vehicle bearing a mobile communication device.
Further in accordance with a preferred embodiment of the present invention, the identification of a mobile communication cell includes at least one of the following identification information elements: an ID of the cell, a cell sector, and a time advance parameter characterizing communication between the mobile communication device and the cell""s base station.
Further in accordance with a preferred embodiment of the present invention, the historical location information includes historical traffic information including at least one traffic parameter characterizing at least one road segment for at least one point of time in the past.
Still further in accordance with a preferred embodiment of the present invention, the information regarding a sequence includes a time-stamped identification of at least one pair of adjacent cells between which the user has passed.
Still further in accordance with a preferred embodiment of the present invention, the mobile communication network interface receives at least some of the location information used by the traffic monitor, from a cellular switch.
Further in accordance with a preferred embodiment of the present invention, the congestion detector employs the historical location information to anticipate future locations of mobile communication devices.
Still further in accordance with a preferred embodiment of the present invention, the at least one routes include a plurality of routes joining a single origin to a single destination.
Additionally in accordance with a preferred embodiment of the present invention, the deviation criterion includes deeming as a travel time deviation, an increase in travel time over a route which affects the relative attractiveness of the route relative to at least one alternative route.
Further in accordance with a preferred embodiment of the present invention, the traffic monitor is also operative to receive speed data derived from a change in at least one parameter, such as but not limited to communication frequency and/or rate of data transfer, characterizing communication between at least one mobile communication device and a base station serving it and to compute at least one traffic-characterizing parameter at least partly based on the speed data.
The term xe2x80x9ctraffic informationxe2x80x9d refers to any type of information describing an effect of the traffic on an individual, such as information defining a desired route for the individual, given the traffic on the various alternative routes, and/or the estimated time of arrival of a vehicle at its destination, given the traffic en route.
The term xe2x80x9croad routexe2x80x9d refers to the sequence of streets or roads followed by an individual vehicle.
The term xe2x80x9ctraffic elementxe2x80x9d may refer to the general population of transmitting vehicles, as opposed to pedestrians, but preferably refers to only those vehicles which advance within the general traffic pattern, as opposed, e.g. to emergency vehicles.
The term xe2x80x9cmobile userxe2x80x9d refers to a user of a mobile communication device.